昨天說到，如果二元搜尋樹是 skewed tree 的話，那麼 insert / delete / search 有可能就會因此變成 O(n) 時間。
因此，若能將高度平衡，即可以讓其時間在 O(logn) 等級。

AVL Tree

前言

其實 AVL Tree 不是甚麼樹縮寫，而是發明者的縮寫（Adelson-Velsky and Landis）

定義

是一棵二元搜尋樹（Binary Search Tree），可為空樹，若非空，則：

1. 令 root 左子樹的高度為 HL，右子樹的高度為HR，則：|HL - HR| <= 1
2. 左右子樹皆為 AVL Tree

平衡係數（Balanced Factor, BF）

每個節點的平衡係數，等於 HL - HR。
根據定義，AVL Tree 所有節點的平衡係數只能是三種數值：-1、0、1
圖示：
（來源：https://en.wikipedia.org/wiki/AVL_tree）

AVL tree node 的插入（insert）

1. 因為 AVL tree 是一棵二元搜尋樹，因此先照 BST 的規則將節點插入後，沿著該節點向樹根節點尋找第一個 BF 不符合 AVL tree 的節點。令該點叫做支撐點（pivot）。
2. 判斷該如何從 pivot 走到新增的節點，僅需判斷兩個 level，因此 pivot 向下兩個 level，共三個節點進入 rotation。
3. rotation 依照先前判斷的方向，分為 4 個 case：LL, LR, RL, RR
   無論是哪種 case，原則就是：數值中間的當樹根，最大數值當 rchild，最小數值當 lchild，再將原本的子樹接上。

圖示：

1. LL
   
2. LR
   
3. RL
   
4. RR
   

建立 AVL tree

AVL Tree 的建立就是靠不斷的插入節點，在進行 rotation。

例如：2 5 8 4 3 1 依序插入，建立 AVL Tree

解：（紅字為 BF）

AVL tree node 的刪除（delete）

1. 因為 AVL tree 是一棵二元搜尋樹，因此先照 BST 的規則將節點刪除後，沿著刪除節點向樹根節點尋找第一個 BF 不符合 AVL tree 的節點。令該點叫做支撐點（pivot）。
2. 找到 pivot 後，rotation 方向依據高度較高那邊判斷，一樣判斷兩層。
3. rotation 原則：RR RL LL LR 與新增節點是相同。與 insert 不同的是，delete rotation 可能需要做不只一次。

範例：

紅黑樹（red-black tree, RB tree）

這裡只是簡單介紹定義，不會介紹他的操作，因為太麻煩了。

1. 節點非黑即紅
2. 空節點是為黑節點
3. root 必為黑節點
4. 紅節點的兩個子點必為黑點
5. 每個 root 到樹葉的路徑所經過的黑節點數相同（具有相同的黑樹高 Black Height）。紅黑樹的平衡是依據黑色樹高在平衡的。

總結

二元樹允許很多形式，但當樹呈現斜曲時，可能會讓操作時間變久。透過 rotation 將 BST 轉換為 RB tree 或 AVL Tree，可以讓樹保持平衡，時間在 O(logn)等級。

明天則是來介紹另一種二元樹的結構： Heap